Algorytm eliminacji Gaussa
Algorytm eliminacji Gaussa jest podstawowym najszerzej znanym algorytmem rozwiązywania układów równań liniowych.
Algorytm eliminacji, zwany algorytmem Gaussa został wynaleziony w Chinach w roku 179. W Europie algorytm zaczął być używany w roku 1771 przez Leonarda Eulera, który nazywał go najbardziej naturalnym sposobem rozwiązywania układów równań. Jest on niesłusznie nazywany algorytmem eliminacji Gaussa, od matematyka Carla Friedricha Gaussa (1777-1855), który nie żył jeszcze w roku 1771 [1].
\( \begin{bmatrix} \int{B^x_{1,p}B^x_{1,p}}dx & \int{B^x_{1,p}B^x_{2,p}}dx & \cdots & \int{B^x_{1,p}B^x_{5,p}}dx \\ \int{B^x_{2,p}B^x_{1,p}}dx & \int{B^x_{2,p}B^x_{2,p}}dx & \cdots & \int{B^x_{2,p}B^x_{5,p}}dx\\ \vdots & \vdots & \vdots & \vdots \\ \int{B^x_{5,p}B^x_{1,p}}dx & \int{B^x_{5,p}B^x_{2,p}}dx & \cdots & \int{B^x_{5,p}B^x_{5,p}}dx \\ \end{bmatrix} \begin{bmatrix} u_{1} \\ u_{2} \\ \vdots \\ u_{5} \\ \end{bmatrix} =\begin{bmatrix} 1 \\ 1 \\ 1 \\ 1 \\ 1 \end{bmatrix} \)
co po scałkowaniu, zgodnie z przekształceniami przedstawionymi w rozdziale 1 daje macierz
\( \begin{bmatrix} \frac{1}{20} & \frac{13}{120} & \frac{1}{120} & 0 & 0 \\ \frac{13}{120} & \frac{1}{2} & \frac{13}{60} & \frac{1}{120} & 0 \\ \frac{1}{120} & \frac{13}{60} & \frac{11}{20} & \frac{13}{60} & \frac{1}{120} \\ 0 & \frac{1}{120} & \frac{13}{60} & \frac{1}{2} & \frac{13}{120} \\ 0 & 0 & \frac{1}{20} & \frac{13}{120} & \frac{1}{120} \\ \end{bmatrix} \begin{bmatrix} u_{1} \\ u_{2} \\ u_{3} \\ u_{4} \\ u_{5} \\ \end{bmatrix} = \begin{bmatrix} 1 \\ 1 \\ 1 \\ 1 \\ 1 \end{bmatrix} \)
Zaczynamy od przekonwertowania macierzy na liczby zmiennoprzecinkowe
\( \begin{bmatrix} 0.05 & 0.10833 & 0.00833 & 0 & 0 \\ 0.10833 & 0.5 & 0.21666 & 0.00833 & 0 \\ 0.00833 & 0.21666 & 0.55 & 0.21666 & 0.00833 \\ 0 & 0.00833 & 0.21666 & 0.5 & 0.10833 \\ 0 & 0 & 0.00833 & 0.10833 & 0.05\\ \end{bmatrix} \begin{bmatrix} u_{1} \\ u_{2} \\ u_{3} \\ u_{4} \\ u_{5} \\ \end{bmatrix} = \begin{bmatrix} 1 \\ 1 \\ 1 \\ 1 \\ 1 \end{bmatrix} \)
Zaczynamy od przeskalowania pierwszego wiersza tak, aby na przekątnej znalazła się jedynka. Innymi słowy przemnażamy pierwszy wiersz przez odwrotność wyrazu z przekątnej. Używamy tutaj konwekcji pseudokodu w której na prawej stronie podstawienia opisujemy sposób modyfikacji wiersza, a na lewej stronie umieszczamy wiersy do którego podstawiamy wynik
\( 1^{st}=1^{st}\frac{1}{A_{1,1}}= 1^{st}\frac{1}{0.05}=1^{st}20 \)
\( \begin{bmatrix} {\color{red}20*}0.05 & {\color{red}20*}0.10833 & {\color{red}20*} 0.00833 & {\color{red}20*}0 & {\color{red}20*}0 \\ 0.10833 & 0.5 & 0.21666 & 0.00833 & 0 \\ 0.00833 & 0.21666 & 0.55 & \frac{13}{60} & 0.00833 \\ 0 & 0.00833 & 0.21666 & 0.5 & 0.10833 \\ 0 & 0 & 0.00833 & 0.10833 & 0.05 \\ \end{bmatrix} \begin{bmatrix} u_{1} \\ u_{2} \\ u_{3} \\ u_{4} \\ u_{5} \\ \end{bmatrix} = \begin{bmatrix} {\color{red}20*}1 \\ 1 \\ 1 \\ 1 \\ 1 \end{bmatrix} \)
\( \begin{bmatrix} {\color{red}1} & {\color{red}2.16666} & {\color{red}0.16666} & {\color{red}0} & {\color{red}0} \\ {\color{blue}0.10833} & 0.5 & 0.21666 & 0.00833 & 0 \\ 0.00833 & 0.21666 & 0.55 & \frac{13}{60} & 0.00833 \\ 0 & 0.00833 & 0.21666 & 0.5 & 0.10833 \\ 0 & 0 & 0.00833 & 0.10833 & 0.05\\ \end{bmatrix} \begin{bmatrix} u_{1} \\ u_{2} \\ u_{3} \\ u_{4} \\ u_{5} \\ \end{bmatrix} = \begin{bmatrix} {\color{red}20} \\ 1 \\ 1 \\ 1 \\ 1 \end{bmatrix} \)
Następnie odejmujemy pierwszy wiersz od drugiego wiersza, przeskalowanego w taki sposób żeby uzyskać zero pod przekątną (w pierwszej kolumnie). Inny słowy wykonujemy operacji
\( 2^{nd} = 2^{nd} - 1^{st} A_{2,1}= 2^{nd} - 1^{st} *{\color{blue}0.10833} \)
\( \begin{bmatrix} 1 & 2.16666 & 0.16666 & 0 & 0 \\ 0.10833{\color{red}-1*0.10833} & 0.5{\color{red}-2.16666*0.10833} & 0.21666{\color{red}-0.16666*0.10833} & 0.00833{\color{red}-0} & 0{\color{red}-0} \\ 0.00833 & 0.21666 & 0.55 & \frac{13}{60} & 0.00833 \\ 0 & 0.00833 & 0.21666 & 0.5 & 0.10833 \\ 0 & 0 & 0.00833 & 0.10833 & 0.05\\ \end{bmatrix} \\ \begin{bmatrix} u_{1} \\ u_{2} \\ u_{3} \\ u_{4} \\ u_{5} \\ \end{bmatrix} = \begin{bmatrix} 20 \\ 1{\color{red}-20*0.10833} \\ 1 \\ 1 \\ 1 \end{bmatrix} \)
W wierszu drugim w kolumnie 4tej odejmujemy 0, w kolumnie 5tej odejmujemy zero od zera
\( \begin{bmatrix} 1 & 2.16666 & 0.16666 & 0 & 0 \\ {\color{red}0} & {\color{red}0.26528} & {\color{red}0.19860} & {\color{red}0.00833} & {\color{red}0} \\ {\color{blue}0.00833} & 0.21666 & 0.55 & \frac{13}{60} & 0.00833 \\ 0 & 0.00833 & 0.21666 & 0.5 & 0.10833 \\ 0 & 0 & 0.00833 & 0.10833 & 0.05 \\ \end{bmatrix} \begin{bmatrix} u_{1} \\ u_{2} \\ u_{3} \\ u_{4} \\ u_{5} \\ \end{bmatrix} = \begin{bmatrix}20 \\ {\color{red}-1.1666} \\ 1 \\ 1 \\ 1 \end{bmatrix} \)
Podobnie odejmujemy pierwszy wiersz od trzeciego wiersza, przeskalowanego w taki sposób żeby uzyskać zero pod przekątną (w pierwszej kolumnie). Inny słowy wykonujemy
\( 3^{rd} = 3^{rd} - 1^{st} A_{3,1}= 3^{rd} - 1^{st} {\color{blue}0.00833} \)
\( \begin{bmatrix} 1 & 2.16666 & 0.16666 & 0 & 0 \\ 0 & 0.26528 & 0.19860 & 0.00833 & 0 \\ 0.00833{\color{red}-1*0.00833} & 0.21666{\color{red}-2.16666*0.00833} & 0.55{\color{red}-0.16666*0.00833} & 0.21666{\color{red}-0} & 0.00833{\color{red}-0} \\ 0 & 0.00833 & 0.21666 & 0.5 & 0.10833 \\ 0 & 0 & 0.00833 & 0.10833 & 0.05 \\ \end{bmatrix} \\ \begin{bmatrix} u_{1} \\ u_{2} \\ u_{3} \\ u_{4} \\ u_{5} \\ \end{bmatrix} = \begin{bmatrix} 20 \\ {\color{red}-1.1666} \\ 1{\color{red}-20*0.00833} \\ 1 \\ 1 \end{bmatrix} \)
\( \begin{bmatrix} 1 & 2.16666 & 0.16666 & 0 & 0 \\ 0 & 0.26528 & 0.19860 & 0.00833 & 0 \\ {\color{red}0} & {\color{red}0.19861} & {\color{red}0.54861} & {\color{red}0.21666} & {\color{red}0.00833} \\ 0 & 0.00833 & 0.21666 & 0.5 & 0.10833\\ 0 & 0 & 0.00833 & 0.10833 & 0.05\\ \end{bmatrix} \begin{bmatrix} u_{1} \\ u_{2} \\ u_{3} \\ u_{4} \\ u_{5} \\ \end{bmatrix} = \begin{bmatrix} 20 \\ -1.1666 \\ {\color{red}0.83333} \\ 1 \\ 1 \end{bmatrix} \)
Przerywamy proces odejmowania pierwszego wiersza od pozostałych, ponieważ w kolejnych wierszach (czwartym i piątym) na przekątnej znajdują się już zera.
Teraz, będziemy przeskalowywać drugi wiersz tak żeby użyć go za chwilę do generacji zer w drugiej kolumnie. Mnożymy najpierw drugi wiersz przez odwrotność wyrazu z przekątnej
\( 2^{nd} = 2^{nd} \frac{1}{A_{2,2}}=2^{nd}\frac{1}{0.26528}=2^{nd}3,76963 \)
\( \begin{bmatrix} 1 & 2.16666 & 0.16666 & 0 & 0 \\ 0 & 0.26528{\color{red}*3,76963} & 0.19860{\color{red}*3,76963} & 0.00833{\color{red}*3,76963} & 0 \\ 0 & 0.19861 & 0.54861 & 0.21666 & 0.00833 \\ 0 & 0.00833 & 0.21666 & 0.5 & 0.10833 \\ 0 & 0 & 0.00833 & 0.10833 & 0.05 \\ \end{bmatrix} \begin{bmatrix} u_{1} \\ u_{2} \\ u_{3} \\ u_{4} \\ u_{5} \\ \end{bmatrix} = \begin{bmatrix} 20 \\ -1.1666{\color{red}*3,76963} \\ 0.83333 \\ 1 \\ 1 \end{bmatrix} \)
\( \begin{bmatrix} 1 & 2.16666 & 0.16666 & 0 & 0 \\ 0 & {\color{red}1} & {\color{red}0.74864} & {\color{red}0.03140} & 0 \\ 0 & {\color{blue}0.19861} & 0.54861 & 0.21666 & 0.00833 \\ 0 & 0.00833 & 0.21666 & 0.5 & 0.10833\\ 0 & 0 & 0.00833 & 0.10833 & 0.05 \\ \end{bmatrix} \begin{bmatrix} u_{1} \\ u_{2} \\ u_{3} \\ u_{4} \\ u_{5} \\ \end{bmatrix} = \begin{bmatrix} 20 \\ {\color{red}-4.39765} \\ 0.83333 \\ 1 \\ 1 \end{bmatrix} \)
Następnie odejmujemy drugi wiersz od trzeciego wiersza, przeskalowanego w taki sposób żeby uzyskać zero pod przekątną (w drugiej kolumnie). Inny słowy wykonujemy operacji
\( 3^{rd} = 3^{rd} - 2^{nd} A_{3,2}= 3^{rd} - 2^{st}{\color{blue}0.19861} \)
\( \begin{bmatrix} 1 & 2.16666 & 0.16666 & 0 & 0 \\ 0 & 1 & 0.74864 & 0.03140 & 0 \\ 0 & 0.19861{\color{red}-1*0.19861} & 0.54861{\color{red}-0.74864*0.19861} & 0.21666{\color{red}-0.03140*0.19861} & 0.00833{\color{red}-0} \\ 0 & 0.00833 & 0.21666 & 0.5 & 0.10833 \\ 0 & 0 & 0.00833 & 0.10833 & 0.05 \\ \end{bmatrix} \\ \begin{bmatrix} u_{1} \\ u_{2} \\ u_{3} \\ u_{4} \\ u_{5} \\ \end{bmatrix} = \begin{bmatrix} 20 \\ -4.39765 \\ 0.83333{\color{red}+4.39765*0.19861} \\ 1 \\ 1 \end{bmatrix} \)
\( \begin{bmatrix} 1 & 2.16666 & 0.16666 & 0 & 0 \\ 0 & 1 & 0.74864 & 0.03140 & 0 \\ 0 & {\color{red}0} & {\color{red}0.39992} & {\color{red}0.21042} & {\color{red}0.00833} \\ 0 & {\color{blue}0.00833} & 0.21666 & 0.5 & 0.10833 \\ 0 & 0 & 0.00833 & 0.10833 & 0.05 \\ \end{bmatrix} \begin{bmatrix} u_{1} \\ u_{2} \\ u_{3} \\ u_{4} \\ u_{5} \\ \end{bmatrix} = \begin{bmatrix} 20 \\ -4.39765 \\ {\color{red}1.70674} \\ 1 \\ 1 \end{bmatrix} \)
Używamy teraz drugiego wiersza żeby wygenerować zero w drugiej kolumnie w wierszu czwartym. W tym celu odejmujemy drugi wiersz przeskalowany przez wartość 0.00833
\( 4^{th}=4^{th}-2^{nd}A_{4,2}=4^{th}-2^{nd}{\color{blue}0.00833} \)
\( \begin{bmatrix} 1 & 2.16666 & 0.16666 & 0 & 0 \\ 0 & 1 & 0.74864 & 0.03140 & 0 \\ 0 & 0 & 0.39992 & 0.21042 & 0.00833 \\ 0 & 0.00833{\color{red}-1*0.00833} & 0.21666{\color{red}-0.74864*0.00833} & 0.5{\color{red}-0.03140*0.00833} & 0.10833 {\color{red}-0} \\ 0 & 0 & 0.00833 & 0.10833 & 0.05 \\ \end{bmatrix} \\ \begin{bmatrix} u_{1} \\ u_{2} \\ u_{3} \\ u_{4} \\ u_{5} \\ \end{bmatrix} = \begin{bmatrix}20 \\ -4.39765 \\ 1.70674 \\ 1{\color{red}+4.39765*0.00833} \\ 1 \end{bmatrix} \)
\( \begin{bmatrix} 1 & 2.16666 & 0.16666 & 0 & 0 \\ 0 & 1 & 0.74864 & 0.03140 & 0 \\ 0 & 0 & 0.39992 & 0.21042 & 0.00833 \\ 0 & {\color{red}0} & {\color{red}0.21042} & {\color{red}0.499738} &{\color{red}0.10833} \\ 0 & 0 & 0.00833 & 0.10833 & 0.05 \\ \end{bmatrix} \begin{bmatrix} u_{1} \\ u_{2} \\ u_{3} \\ u_{4} \\ u_{5} \\ \end{bmatrix} = \begin{bmatrix}20 \\ -4.39765 \\ 1.70674 \\ {\color{red}1.03663} \\ 1 \end{bmatrix} \)
Zostały nam do wygenerowania trzy zera, w wyrazach \( A_{4,3}, A_{5,3}\textrm{ oraz w }A_{5,4} \)
W tym celu użyjemy trzeciego wiersza, przeskalujemy go najpierw tak żeby na przekątnej dostać wartość 1
\( 3^{rd}=3^{rd}\frac{1}{A_{3,3}}=3^{rd}\frac{1}{0.39992}=3^{rd}2.50050 \)
\( \begin{bmatrix} 1 & 2.16666 & 0.16666 & 0 & 0 \\ 0 & 1 & 0.74864 & 0.03140 & 0 \\ 0 & 0 & 0.39992{\color{red}*2.50050} & 0.21042{\color{red}*2.50050} & 0.00833{\color{red}*2.50050} \\ 0 & 0 & 0.21042 & 0.499738 & 0.10833 \\ 0 & 0 & 0.00833 & 0.10833 & 0.05 \\ \end{bmatrix} \begin{bmatrix} u_{1} \\ u_{2} \\ u_{3} \\ u_{4} \\ u_{5} \\ \end{bmatrix} = \begin{bmatrix}20 \\ -4.39765 \\ 1.70674{\color{red}*2.50050} \\ 1.03663 \\ 1 \end{bmatrix} \)
\( \begin{bmatrix} 1 & 2.16666 & 0.16666 & 0 & 0 \\ 0 & 1 & 0.74864 & 0.03140 & 0 \\ 0 & 0 & {\color{red}1} & {\color{red}0.52615} & {\color{red}0.02082} \\ 0 & 0 & 0.21042 & 0.499738 & 0.10833 \\ 0 & 0 & 0.00833 & 0.10833 & 0.05 \\ \end{bmatrix} \begin{bmatrix} u_{1} \\ u_{2} \\ u_{3} \\ u_{4} \\ u_{5} \\ \end{bmatrix} = \begin{bmatrix}20 \\ -4.39765 \\ {\color{red}4.2677} \\ 1.03663 \\ 1 \end{bmatrix} \)
Teraz, trzeci wiersz może zostać użyty do wygenerowania zer w trzeciej kolumnie pod przekątną
\( 4^{rd}=4^{rd}-3^{rd}A_{4,3}=4^{rd}-3^{rd}0.21042 \)
\( \begin{bmatrix} 1 & 2.16666 & 0.16666 & 0 & 0 \\ 0 & 1 & 0.74864 & 0.03140 & 0 \\ 0 & 0 & 1 & 0.52615 & 0.02082 \\ 0 & 0 & 0.21042{\color{red}-1*0.21042} & 0.499738{\color{red}-0.52615*0.21042} & 0.10833{\color{red}-0.02082*0.21042} \\ 0 & 0 & 0.00833 & 0.10833 & 0.05 \\ \end{bmatrix} \nonumber \\ \begin{bmatrix} u_{1} \\ u_{2} \\ u_{3} \\ u_{4} \\ u_{5} \\ \end{bmatrix} = \begin{bmatrix}20 \\ -4.39765 \\ 4.2677 \\ 1.03663{\color{red}-4.2677*0.21042} \\ 1 \end{bmatrix} \)
\( \begin{bmatrix} 1 & 2.16666 & 0.16666 & 0 & 0 \\ 0 & 1 & 0.74864 & 0.03140 & 0 \\ 0 & 0 & 1 & 0.52615 & 0.02082 \\ 0 & 0 & {\color{red}0} & {\color{red}0.38902} & {\color{red}0.10395} \\ 0 & 0 & {\color{blue}0.00833} & 0.10833 & 0.05 \\ \end{bmatrix} \nonumber \\ \begin{bmatrix} u_{1} \\ u_{2} \\ u_{3} \\ u_{4} \\ u_{5} \\ \end{bmatrix} = \begin{bmatrix}20 \\ -4.39765 \\ 4.2677 \\ {\color{red}0.13862} \\ 1 \end{bmatrix} \)
\( 5^{th}=5^{th}-3^{rd}A_{5,3}=5^{th}-3^{rd}{\color{blue}0.00833} \)
\( \begin{bmatrix} 1 & 2.16666 & 0.16666 & 0 & 0 \\ 0 & 1 & 0.74864 & 0.03140 & 0 \\ 0 & 0 & 1 & 0.52615 & 0.02082 \\ 0 & 0 & 0 & 0.38902 & 0.10395 \\ 0 & 0 & 0.00833{\color{red}-1*0.0.00833} & 0.10833{\color{red}-0.52615*0.00833} & 0.05{\color{red}-0.02082*0.00833} \\ \end{bmatrix} \nonumber \\ \begin{bmatrix} u_{1} \\ u_{2} \\ u_{3} \\ u_{4} \\ u_{5} \\ \end{bmatrix} = \begin{bmatrix}20 \\ -4.39765 \\ 4.2677 \\ 0.13862 \\ 1{\color{red}-4.2677*0.00833} \end{bmatrix} \)
\( \begin{bmatrix} 1 & 2.16666 & 0.16666 & 0 & 0 \\ 0 & 1 & 0.74864 & 0.03140 & 0 \\ 0 & 0 & 1 & 0.52615 & 0.02082 \\ 0 & 0 & 0 & 0.38902 & 0.10395 \\ 0 & 0 & {\color{red}0} & {\color{red}0.10394} & {\color{red}0,04982} \\ \end{bmatrix} \nonumber \\ \begin{bmatrix} u_{1} \\ u_{2} \\ u_{3} \\ u_{4} \\ u_{5} \\ \end{bmatrix} = \begin{bmatrix}20 \\ -4.39765 \\ 4.2677 \\ 0.13862 \\ {\color{red}0,96445} \end{bmatrix} \)
W ostatnim kroku skalujemy czwarty wiersz
\( 4^{th}=4^{th}\frac{1}{A_{4,4}}=4^{th}\frac{1}{0.38902}=4^{th}2.57056 \)
\( \begin{bmatrix} 1 & 2.16666 & 0.16666 & 0 & 0 \\ 0 & 1 & 0.74864 & 0.03140 & 0 \\ 0 & 0 & 1 & 0.52615 & 0.02082 \\ 0 & 0 & 0 & 0.38902{\color{red}*2.57056} & 0.10395{\color{red}*2.57056} \\ 0 & 0 & 0 & 0.10394 & 0,04982 \\ \end{bmatrix} \nonumber \\ \begin{bmatrix} u_{1} \\ u_{2} \\ u_{3} \\ u_{4} \\ u_{5} \\ \end{bmatrix} = \begin{bmatrix} 20 \\ -4.39765 \\ 4.2677 \\ 0.13862{\color{red}*2.57056} \\ 0,96445\end{bmatrix} \)
\( \begin{bmatrix} 1 & 2.16666 & 0.16666 & 0 & 0 \\ 0 & 1 & 0.74864 & 0.03140 & 0 \\ 0 & 0 & 1 & 0.52615 & 0.02082 \\ 0 & 0 & 0 & {\color{red}1} & {\color{red}0.26721} \\ 0 & 0 & 0 & {\color{blue}0.10394} & 0,04982 \\ \end{bmatrix} \nonumber \\ \begin{bmatrix} u_{1} \\ u_{2} \\ u_{3} \\ u_{4} \\ u_{5} \\ \end{bmatrix} = \begin{bmatrix} 20 \\ -4.39765 \\ 4.2677 \\ {\color{red}0.35633
\n} \\ 0.96445\end{bmatrix} \)
I w końcu odejmujemy czwarty wiersz od piątego tak żeby uzyskać zero na pozycji \( A_{5,4} \)
\( 5^{th}=5^{th}-4^{th}{\color{blue}0.10394} \)
\( \begin{bmatrix} 1 & 2.16666 & 0.16666 & 0 & 0 \\ 0 & 1 & 0.74864 & 0.03140 & 0 \\ 0 & 0 & 1 & 0.52615 & 0.02082 \\ 0 & 0 & 0 & 1 & 0.26721 \\ 0 & 0 & 0 & 0.010394{\color{red}-1*0.010394}\ & 0,04982{\color{red}-0.26721*0.010394} \\ \end{bmatrix} \\ \begin{bmatrix} u_{1} \\ u_{2} \\ u_{3} \\ u_{4} \\ u_{5} \\ \end{bmatrix} = \begin{bmatrix}20 \\ -4.39765 \\ 4.2677 \\ 0.35633 \\ 0.96445{\color{red}-2.43385*0.010394}\end{bmatrix} \)
\( \begin{bmatrix} 1 & 2.16666 & 0.16666 & 0 & 0 \\ 0 & 1 & 0.74864 & 0.03140 & 0 \\ 0 & 0 & 1 & 0.52615 & 0.02082 \\ 0 & 0 & 0 & 1 & 0.26721 \\ 0 & 0 & 0 & {\color{red}0}\ & {\color{red}0.04704} \\ \end{bmatrix} \nonumber \\ \begin{bmatrix} u_{1} \\ u_{2} \\ u_{3} \\ u_{4} \\ u_{5} \\ \end{bmatrix} = \begin{bmatrix}20 \\ -4.39765 \\ 4.2677 \\ 0.35633 \\ {\color{red}0.93915}\end{bmatrix} \)
Na końcu możemy przeskalować wiersz piąty żeby miał jedynkę na przekątnej
\( 5^{th}=5^{th}-\frac{1}{A_{5,5}}=5^{th}\frac{1}{0,04704}=5^{th}21,2585 \)
\( \begin{bmatrix} 1 & 2.16666 & 0.16666 & 0 & 0 \\ 0 & 1 & 0.74864 & 0.03140 & 0 \\ 0 & 0 & 1 & 0.52615 & 0.02082 \\ 0 & 0 & 0 & 1 & 0.26721 \\ 0 & 0 & 0 & 0\ & 0.047042{\color{red}*21,2585} \\ \end{bmatrix} \nonumber \\ \begin{bmatrix} u_{1} \\ u_{2} \\ u_{3} \\ u_{4} \\ u_{5} \\ \end{bmatrix} = \begin{bmatrix}20 \\ -4.39765 \\ 4.2677 \\ 0.35633 \\ {\color{red}0.93915*21.258}\end{bmatrix} \)
\( \begin{bmatrix} 1 & 2.16666 & 0.16666 & 0 & 0 \\ 0 & 1 & 0.74864 & 0.03140 & 0 \\ 0 & 0 & 1 & 0.52615 & 0.02082 \\ 0 & 0 & 0 & 1 & 0.26721 \\ 0 & 0 & 0 & 0\ & {\color{red}1} \\ \end{bmatrix} \nonumber \\ \begin{bmatrix} u_{1} \\ u_{2} \\ u_{3} \\ u_{4} \\ u_{5} \\ \end{bmatrix} = \begin{bmatrix}20 \\ -4.39765 \\ 4.2677 \\ 0.35633 \\ {\color{red}19.96445}\end{bmatrix} \)
W ten sposób uzyskaliśmy macierz trójkątną górną.
Algrorytm który wykonywaliśmy krok po kroku podsumować można w następujący sposób:
1 for irow=1,N //pętla po wierszach
2 for icol=irow+1,N // skalowanie wiersza
3 A(irow,icol)=A(irow,icol)/A(irow,irow)
4 end loop
5 b(irow)=b(irow)/A(irow,irow)
6 A(irow,irow)=1.0
7 for irow2=irow+1,N //odejmowanie wierszy
8 for icol=irow2+1,N
9 A(irow2,icol) = A(irow2,icol) - A(irow2,irow) * A(irow,icol)
10 end loop
11 b(irow2)=b(irow2)-A(irow2,irow)*b(irow2)
12 A(irow2,irow)=0
13 end loop
14 end loop
Ostatni krok to uruchomienie algorytmu podstawiania wstecz, który rozwiąże nasz układ równań począwszy od ostatniego równania.
Innymi słowy nasz układ równań
\( \begin{bmatrix} 1 & 2.16666 & 0.16666 & 0 & 0 \\ 0 & 1 & 0.74864 & 0.03140 & 0 \\ 0 & 0 & 1 & 0.52615 & 0.02082 \\ 0 & 0 & 0 & 1 & 0.26721 \\ 0 & 0 & 0 & 0\ & 1 \\ \end{bmatrix} \nonumber \\ \begin{bmatrix} u_{1} \\ u_{2} \\ u_{3} \\ u_{4} \\ u_{5} \\ \end{bmatrix} = \begin{bmatrix} 20 \\ -4.39765 \\ 4.2677 \\ 0.35633 \\ 19.96445 \end{bmatrix} \)
Rozpisujemy
\( 1u_1+2.16666u_2+0.16666u_3=20 \\ 1u_2+0.74864u_3+0.03140u_4=-4.39765 \\ 1u_3+0.52615u_4+0.02082u_5=4.2677 \\ 1u_4+0.26721u_5=0.35633 \\ 1u_5=19.96445 \)
I rozwiązujemy od ostatniego równania
\( u_5 = {\color{red}19.96445} \\ u_4 = 0.35633-0.26721u_5=0.35633-0.26721*{\color{red}19.96445} \\ ={\color{blue}-4.97837} \\ u_3 = 4.2677-0.52615u_4-0.02082u_5 \\ =4.2677-0.52615*{\color{blue}(-4.97837)} -0.02082*{\color{red}19.96445}={\color{green}6.47140} \\ u_2 = -4.39765-0.74864u_3-0.03140u_4 \\ =-4.39765-0.74864*{\color{green}6.47140}-0.03140*{\color{blue}(-4.97837)} ={\color{cyan}-2.61466} \\ u_1 = 20 - 2.16666u_2-0.16666u_3 \\ =20 - 2.16666*{\color{cyan}(-2.61466)}-0.16666*{\color{green}6.47140}=24.58655 \)
Zróbmy teraz następujące obserwacje.
Jeśli uruchomimy na przykład MATLABa (lub darmową wersje OCTAVE) i wprowadzimy naszą macierz
A=[1/20 13/120 1/120 0 0 ; 13/120 1/2 13/60 1/120 0; 1/120 13/60 11/20 13/60 1/120; 0 1/120 13/60 1/2 13/120; 0 0 1/120 13/120 1/120]
oraz wektor prawej strony
b=[1 1 1 1 1]
i rozwiążemy układ równań solwerem napisanym w MATLABie (autorstwa Tima Davisa z Uniwersytetu na Florydzie, w którym operacja rozwiązania układu równań oznaczona jest backslashem \( \backslash \)) dostaniemy trochę inne rozwiązanie
x=A\b'
x=42.0588, -10.8824, 9.1176, -10.8824, 42.0588
Powodem jest fakt iż w naszym algorytmie zignorowaliśmy tak zwany pivoting. Algorytm eliminacji Gaussa działa bez pivotingu gdy macierz posiada pewne specyficzne właściwości, to znaczy jeśli jest symetryczna i dodatnio określona.
Jeśli macierz nie jest symetryczna lub nie jest dodatnio określona, algorytm eliminacji Gaussa bez pivotingu w niektórych przypadkach działa, a w niektórych nie działa. W naszym przypadku macierz jest symetryczna, ale nie jest dodatnio określona, co w szczególności objawia się faktem iż wyrazy z przekątnej mają większe wartości niż wyrazy spoza przekątnej. W naszym przypadku tak nie jest, na przykład wyraz \( A_{1,1}=0.05 \) zaznaczone na czerwone są mniejsze niż na przykład wyrazy \( A_{1,2}=A_{2,1}=0.10833 \) (zaznaczone na niebiesko).
\( \begin{bmatrix} {\color{red}0.05} & {\color{blue}0.10833} & 0.00833 & 0 & 0 \\ {\color{blue}0.10833}& 0.5 & 0.21666 & 0.00833 & 0 \\ 0.00833 & 0.21666 & 0.55 & 0.21666 & 0.00833 \\ 0 & 0.00833 & 0.21666 & 0.5 & 0.10833 \\ 0 & 0 & 0.00833 & 0.10833 & 0.05\\ \end{bmatrix} \)
W takim przypadku algorytm eliminacji Gaussa popełni duży błąd dzieląc np. pierwszy wiersz przez mały wyraz z przekątnej \( A_{1,1}=0.05 \) Dzieje się tak dlatego iż nasze liczby przechowujemy w komputerze w sposób przybliżony, obcinając na przykład wszystko co znajduje się za piątym miejscem po przecinku. Żeby poprawić nasz błąd, należy dodać do algorytmu eliminacji Gaussa pivoting.
Algorytm eliminacji Gaussa jest kosztowny. Oznacza to że dla macierzy o rozmiarze \( N \) wierszy i kolumn, wykona on około \( N^3 \) operacji. Jaką więc największą macierz możemy przetworzyć algorytmem eliminacji Gaussa w ciągu 24 godzin? Na dzień dzisiejszy (styczeń 2019) zegary procesorów mają około 3 GHz. Oznacza to iż w ciągu każdej sekundy procesor potrafi wykonać \( 3\times 10^9 \) dodawań lub mnożeń. Doba ma \( 24*60*60=86400 \) sekund. Procesor potrafi więc wykonać \( 86400*10^9=86400000000000 \) operacji dodawania i mnożenia wciągu doby. Pierwiastek trzeciego stopnia z tej liczby to \( (86400000000000)^{\frac{1}{3}}\approx44208 \) tak więc największa macierz którą potrafimy przetworzyć ma rozmiar 44208. Reprezentuje ona siatkę obliczeniową o 210 elementach w każdym kierunku. Jest to więc względnie mała siatka obliczeniowa. Potrzebujemy lepszych algorytmów. Co więcej wszystkie nasze szacowania przeprowadziliśmy przy założeniu że procesor nie czeka na dane, tylko cały czas je przetwarza, oraz że posiadamy wystarczająco dużo pamięci RAM oraz optymalną strukturę cache'a procesora. Zazwyczaj sytuacji nie jest tak idealna, w praktyce więc trudno jest przetworzyć eliminacją Gaussa macierze o rozmiarze większym niż 10000 co odpowiada siatce 100 na 100.
W przypadku wielu prawych stron, dla każdej prawej strony konieczne jest wykonywanie eliminacji Gaussa ponownie. Możliwe jest zapamiętanie liczb przez które przemnażamy prawą stronę, tak żeby wykonować eliminację tylko raz, i dla każdej nowej prawej strony wykonać jedynie update. Wykonuje to algorytm LU faktoryzacji.
Algorytm eliminacji Gaussa nie opuszcza zer. Przemnażanie zer przez liczby niezerowe nie ma generalnie sensu, jest stratą czasu. Algorytm elimiancji Gaussa można przyspieszyć opuszczając wszystkie zera. Jeśli będziemy wiedzieć apriori gdzie w macierzy znajdują się zera, możemy je opuścić i przyspieszyć elimiancję Gaussa. To będzie przedmiotem algorytmu frontalnego i wielo-frontalnego.
Jeśli macierz posiada strukturę produktu Kroneckera dwóch mniejszych macierzy (co miało miejsce w przykładzie z rozdziału pierwszego) wówczas możliwe jest zastosowanie algorytmu solwera zmienno-kierunkowego, o liniowej złożoności obliczeniowej.
Jeśli zadowala nas wynik z pewną dokładnością, np. 0.0001, możliwe jest obliczenie rozwiązania przybliżonego stosując tak zwane algorytmy iteracyjne. Jednakże algorytmy te nie działają dla wszystkich rodzajów macierzy.